Theory of Computation
Q161.
Which of the following languages is/are regular? L_{1}:\{wxw^{R}|w,x \in \{a,b\}^{*} \; and \; |w|,|x| \gt 0 \}, w^{R} is the reverse of string w L_{2}:\{a^{n}b^{m}|m\neq n \; and \; m,n\geq 0\} L_{3}:\{a^{p}b^{q}c^{r}|p,q,r\geq 0\}Q162.
Which of the following are regular sets? I. \{a^{n}b^{2m}|n\geq 0,m\geq 0\} II. \{a^{n}b^{m}|n=2m\} III. \{a^{n}b^{m}|n\neq m\} IV. \{xcy|x,y,\in \{a,b\}^*\}Q164.
Consider the languages L_{1}=\phi abd L_{2}=\{a\}. Which one of the following represents L_{1} L_{2}^{*} \cup L_{1}^{*}?Q165.
Consider the following statements. I. If L_1\cup L_2 is regular, then both L_1 \; and \; L_2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?Q166.
A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?Q167.
L1 is a recursively enumerable language over \Sigma. An algorithm A effectively enumerates its words as w1, w2, w3, ... define another language L2 over \SigmaU{#} as {wi # wj : wi, wj \in L1, i \lt j}. Here # is a new symbol. Consider the following assertions. S1 : L1 is recursive implies L2 is recursive S2 : L2 is recursive implies L1 is recursive Which of the following statements is true ?Q169.
Let \Sigma=\left\{0,1\right\}, L = \Sigma^* \text{ and } R=\left\{0^n1^n \mid n \gt 0\right\} then the languages L \cup R and R are respectivelyQ170.
Let L be a regular language. Consider the constructions on L below: I. \text{repeat} (L) = \{ww \mid w \in L\} II. \text{prefix} (L) = \{u \mid \exists v : uv \in L\} III. \text{suffix} (L) = \{v \mid \exists u: uv \in L\} IV. \text{half} (L) = \{u \mid \exists v: | v | = | u | \text{ and } uv \in L\} Which choice of L is best suited to support your answer above?